///###############
//FILE          : SortedList.java
//WRITER        : Lior Zimmerman, liorz06, 066462300
//WRITER        : Ohad Dan, ohad_dan, 036767960
//EXERCISE      : oop ex1 2008
//DESCRIPTION   : this class represents a sorted linked list.
//###############
package oop.ex1.sortedStructure;

import java.util.List;
import java.util.ArrayList;

/**
 * A doubly linked list data structure. Holds sorted data. 
 * Enable data access keeping it sorted.
 * @param <Key> Primary key of the list.
 * @param <InfoType> Data type held by the list.
 */
class SortedList
    <Key extends Comparable<Key>, InfoType extends Keyed<Key> > 
    implements SortedStructure<Key, InfoType> {
   
	//*****************************************************
	// Data Members :                                     * 
	//*****************************************************
	protected Node<InfoType> _head, _tail;
    protected int _size;
    
  //*****************************************************
	// Public Methods :                                 * 
	//***************************************************
    /**
	 * Constructs an empty list.
	 */
    public SortedList() {
        _head = null;
        _tail = null;
        _size = 0;
    }
    /**
	 * Copy constructor. Constructs a copy of the given list.
	 */
    public SortedList( SortedList<Key,InfoType> list ) {
        _head = list.getHead();
        _tail = list.getTail();
        _size = list.size();
    }
    /**
     * Returns true if the list is empty, false otherwise.
     * @return True if the list is empty, false otherwise.
     */
    public boolean  isEmpty(){ 
        return _head == null;
    }
    /**
     * Returns list's head.
     * @return List's head.
     */
    protected Node<InfoType> getHead(){
        return _head;
    }
    /**
     * Returns list's tail.
     * @return List's tail.
     */
    protected Node<InfoType> getTail() {
        return _tail;
    }
    /**
	 * Returns the size of the list - number of Nodes.
	 * @return List size.
	 */
    public int size(){ 
        return _size;
    }
    /**
     * Inserts one node before the another.
     * @param node The node to be inserted.
     * @param before To be inserted before this one.
     */
    private void insertBefore( Node<InfoType> node, Node<InfoType> before) {
        if ( before.getPrev() != null ) {
            Node<InfoType> pointer = before.getPrev();
            pointer.setNext(node);
            node.setPrevious(pointer);
        }
        node.setNext(before);
        before.setPrevious(node);
    }
    /**
     * Inserts one node before the another.
     * @param node The node to be inserted.
     * @param after To be inserted after this one.
     */
    private void insertAfter( Node<InfoType> node, Node<InfoType> after) {
        if ( after.getNext() != null ) {
            Node<InfoType> pointer = after.getNext();
            pointer.setPrevious(node);
            node.setNext(pointer);
        }
        after.setNext(node);
        node.setPrevious(after);
    }
    /**
     * Inserts new data.
     * @param data - data to be inserted.
     * @throws SortedStructureNullException case of null insertion.
     * @throws SortedStructureDuplicateException in case the given 
     * data already contained in the list.
     */
    public void insert(InfoType data) throws 
    SortedStructureDuplicateException, SortedStructureNullException{
        //if the data is null, throw an exception
        if ( data == null ) {
            throw new SortedStructureNullException("Null Value inserted");
        }
        Node<InfoType> insertedNode = new Node<InfoType>(data);
        _size++;
        //Empty list.
        if ( _head == null ) { 
            _head = new Node<InfoType>(data);
            _tail = _head;
            return;
            // One node list
        }else if ( _tail == _head ) {
          if ( _head.getData().getKey().compareTo(data.getKey()) < 0) {
        	  //Insert after head.
              _tail = new Node<InfoType>( data);
              _head.setNext(_tail);
              _tail.setPrevious(_head);
              return;
          }else if ( _head.getData().getKey().compareTo(data.getKey()) > 0) {
              //Insert before head.
        	  _tail = new Node<InfoType>( _head.getData() );
              _head.setData(data);
              _head.setNext(_tail);
              _tail.setPrevious(_head);
              return;
        }else { 
            _size--;
            throw new SortedStructureDuplicateException("Duplicate Value" +
        		"inserted");
        }
          
        }
        if ( _head.getData().getKey().compareTo(data.getKey()) > 0 ) {
            insertBefore(insertedNode, _head);
            _head = insertedNode;
            return;
        }else if( _tail.getData().getKey().compareTo(data.getKey()) < 0) {
            insertAfter(insertedNode, _tail);
            _tail = insertedNode;
            return;
        }
        //Regular insertion a node in the middle of the list.
        Node<InfoType> pointer = _head;
        while( pointer != null ) {
            if (pointer.getData().getKey().compareTo(data.getKey()) >0 ) {
                insertBefore(insertedNode,pointer);
                return;
            }else if(pointer.getData().getKey().equals(data.getKey()) ){
            	_size--;
                throw new SortedStructureDuplicateException("Duplicate value " +
                		"inserted");
            }
            pointer = pointer.getNext();
        }

    }
    /**
     * Returns the instance with given key.
     * @param key the key of the desired instance.
     * @return The instance with given key.
     */
    public InfoType get (Key key){ 
        if( _head == null ) { return null; }
        Node<InfoType> holder = _head;
        while ( holder != null ) {
            if ( holder.getData().getKey().equals(key) ) {
                return holder.getData();
            }
            holder = holder.getNext();
        }
        return null;       
    }
    /**
     * Remove an in instance from the list.
     * @param key The key of the instance to be removed.
     * @return The removed instance, or null if given key doedsn't exist.
     */
    public InfoType remove (Key key){ 
    	InfoType removeThis = null;
    	if ( _head == null ) {
    	    return null;
    	}
    	if ( _tail.getData().getKey().equals(key) ){
    		removeThis = _tail.getData();
    		if( _tail.getPrev() != null ) {
    		    _tail = _tail.getPrev();
    		    _tail.setNext(null);
    		}else {
    		    _tail = _head = null;
    		}
    		_size--;
    		return removeThis;
    	}
    	
		Node<InfoType> holder = _head;   	 
		while ( holder.getNext() != null ) {
			if (holder.getData().getKey().equals(key)){
				removeThis = holder.getData();
				Node<InfoType> next = holder.getNext();
				Node<InfoType> prev = holder.getPrev();
				if ( prev != null ) {
				    prev.setNext(next);
				}else {
				    _head = next;
				}
				next.setPrevious(prev);
				_size--;
				return removeThis;
			}  
			holder = holder.getNext();
		}
    	// If no other option was submitted- the key is not in the list.
    	return null; 
    }
    /**
     * Returns all the keys of the list instances.
     * @return A list with all the list's keys.
     */
    public List<Key> getAllKeys(){ 
        if ( _head == null ) {
            return null;
        }
        ArrayList<Key> keys = new ArrayList<Key>();
        Node<InfoType> pointer = _head;
        while ( pointer != null ) {
            keys.add(pointer.getData().getKey());
            pointer = pointer.getNext();
        }
        return keys;
    }
    /**
     * Returns a string representation of the list.
     * @return A String with list's data 
     */
    public String toString() {
    	return "[" + toString(",") + "]";
    }
    /**
     * Returns a string representation of the list.
     * @param sep Separator between two instances. 
     * @return A String with list's data 
     */
    public String toString(String sep){
        if ( sep == null ) {
            sep = ",";
        }
        String returnval="";
        if ( _head == null ) {
            return null;
        }
        Node<InfoType> pointer = _head;
        while ( pointer != null ) {
            returnval += pointer.getData().toString() + sep; 
            pointer = pointer.getNext();
        }
        return returnval.substring(0, returnval.lastIndexOf(sep));
    }
/**
 * this class represents the node of the sorted list.
 * @author liorz06
 * @author ohad.dan
 *
 * @param <Info>
 */
    private class Node<Info> {
    	//***********************************************
    	// Data Members :                               * 
    	//***********************************************
    	InfoType _data;
        Node<Info> _next;
        Node<Info> _prev;
        //*********************************************
        // Methods :                                  * 
        //*********************************************
        /**
         * Constructs an empty node.
         */
        public Node() {
            _data=null;
        }
        /**
         * Constructs a node with the given data.
         * @param data Node's data.
         */
        public Node(InfoType data){
            _data = data;
        }
        /**
         * Constructs a node with the given data.         
         * @param data Node's data.
         * @param next Next node in list.
         */
        public Node( InfoType data, Node<Info> next) {
            _next = next;
            next.setPrevious(this);
            _data = data;
        }
        /**
         * Constructs a node with the given data.         
         * @param data Node's data.
         * @param next Next node in list.
         * @param prev Previous node in list.
         */
        public Node( InfoType data, Node<Info> next, Node<Info> prev) {
            _next = next;
            next.setPrevious(this);
            _prev = prev;
            prev.setNext(this);
            _data = data;
        }
        /**
         * Sets the given node to be the node connected after this.
         * @param next The node after this.
         */
        public void setNext(Node<Info> next) {
            _next = next;
        }
        /**
         * Sets this previous node of this.
         * @param prev The node before this.
         */
        public void setPrevious(Node<Info> prev) {
            _prev = prev;
        }
        /**
         * Returns the node after this.
         * @return The node after this.
         */
        public Node<Info> getNext() {
            return _next;
        }
        /**
         * Returns the node previous to this.
         * @return The node previous to this.
         */
        public Node<Info> getPrev() {
            return _prev;
        }
        /**
         * Returns the data in .
         * @return The node previous to this.
         */
        public InfoType getData(){ 
            return _data;
        }
        /**
         * Sets the data of the node to be the given data.
         * @param data The data to be set to the node.
         */
        public void setData( InfoType data ) {
            _data = data;
        }
    }
}
